import java.util.Arrays;

public class PriorityQueue {

    public int[] elem;

    public int usedSize;

 

    public PriorityQueue(int[] elem,int usedSize) {
        this.elem = elem;
        this.usedSize = usedSize;
    }

 

    /**

     * 建堆的时间复杂度：
     *
     * @param array
     */

    public void createHeap(int[] array) {
        //节点的下标=孩子节点-1/2或者孩子节点-1-1/2
        for (int parent = (usedSize-1-1)/2;parent >= 0;parent--){
            shiftDown(parent,usedSize);
        }
    }

 

    /**
     *
     * @param root 是每棵子树的根节点的下标
     * @param len  是每棵子树调整结束的结束条件
     * 向下调整的时间复杂度：O(logn)
     */

    private void shiftDown(int root,int len) {
        int child = 2 * root + 1;
        //最起码是有有孩子的
        while (child < len){
            //判断其左孩子和其右孩子的大小，但是其前提是必须有右孩子

            //如果孩子的大小超过了其数组的长度 或 呈升序的 child不加加
            if (child+1 < len && elem[child] < elem[child+1]){
                child++;
            }
            //当孩子的值大于根节点的值时，需要交换孩子和根的值
            if (elem[child] > elem[root]){
                swap(elem,child,root);
                root = child;
                child = 2*root+1;//孩子节点=2*根节点+1
            }else{
                break;
            }
        }
    }

    public void swap(int array[],int i ,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
 

    /**
     * 入队：仍然要保持是大根堆
     * @param val
     */

    public void push(int val) {
        if (isFull()){
            //检查数组是否满
            elem = Arrays.copyOf(elem,elem.length*2);//两倍扩容
        }
        this.elem[usedSize] = val;
        usedSize++;
        //直接插入到最后
        shiftUp(usedSize - 1);
    }


    /**
     * 向上调整
     * @param child
     */

    private void shiftUp(int child) {
        //寻找根节点
        int parent = (child - 1)/2;
        while (child > 0){
            //如果孩子节点的值大于父亲节点的值，交换
            if (elem[child] > elem[parent]){
                swap(elem,child,parent);
                child = parent;
                parent = (child - 1)/2;
            }else {
                break;
            }
        }
    }

 

    public boolean isFull() {
        return usedSize == elem.length;
    }

 

    /**
     * 出队【删除】：每次删除的都是优先级高的元素
     * 仍然要保持是大根堆
     */

    public int pollHeap() {
        if (isEmpty()){
            return -1;
        }
        int old = elem[0];
        swap(elem,0,usedSize-1);
        usedSize--;
        shiftDown(0,usedSize);
        return old;
    }

 

    public boolean isEmpty() {
        return usedSize == 0;
    }

 

    /**
     * 获取堆顶元素
     * @return
     */

    public int peekHeap() {
        return elem[0];
    }

}